1. Field of the Invention
The invention relates generally to a method and an apparatus for performing error decoding of digital data using Reed-Solomon codes. More particularly, the invention relates to a method and an apparatus for decoding the value and location of error words in digital data using Reed-Solomon codes by a series of product sum arithmetic operations, without a calculation of power.
2. Technical Background
Reed-Solomon (hereinbelow, abbreviated as RS) codes are very important in communication for the preservation of data, operating to continuously correct errors in bytes of digital data.
There are generally two different circuit types in the design of RS code decoders. One is the pipe-line type and the other is the processor-based program control type. Pipe-line type RS code decoders are typically used in systems that must work at high-speed and in real-time. Correspondingly, the circuitry for the pipe-line type RS code decoder is complex and expensive which is wasteful of resources and money in a system demanding only moderate speed. The RS code decoder of the processor-based program control type performs repeated calculations using an arithmetic logic unit (ALU), under the program control, which reduces the complexity and cost of the circuit of the RS code decoder. There are apparent differences between the pipe-line type and the processor-based program control type RS code decoders.
For RS codes, the calculations for decoding, when there are more than two errors among the transmitted words, are too complex to appropriately use the processor-based program control type of RS code decoder. However, the conventional system of this type for decoding two error words is used and is illustrated hereinafter:
An RS code can be defined as RS.sub.m (n, k). The input terminal of the RS code decoder receives n symbols, with each symbol consisting of m bits. After error correction, k data symbols are transmitted from the decoder.
RS.sub.m (n,k) can be defined as: ##EQU1##
Therefore, in an RS code decoder which can detect two error words, t=2, d=2t+1=5, k=n+1-5=n-4, and RS.sub.m (n,k) can be modified as RS.sub.m (n,n-4). For RS.sub.m (n,n-4) codes, the generating polynomial can be represented as: EQU g(x)=(x-1)(X-.alpha.)(X-.alpha..sup.2) (X-.alpha..sup.3)
It may be assumed that in the n symbols there are v error words which are located at l.sub.1, l.sub.2, l.sub.3, l.sub.4, . . . , l.sub.v and whose values are respectively Y.sub.1, Y.sub.2, Y.sub.3, Y.sub.4, . . . , Y.sub.v. In order to explain the principle of decoding the RS codes hereinafter, if the location l.sub.i is known before the n symbols are decoded, the error word is defined as an `erasure`, and if the location l.sub.i is unknown before the n symbols are decoded, the error word is defined as an `error`.
With RS codes having a Hamming distance (d=5), p error words and q erasure words can be detected if p and q satisfy the following formula: EQU 2p+q .ltoreq.d-1=5-1=4 (1)
And if X.sub.i =.alpha..sup.li 1.ltoreq.i.ltoreq.v,
then the syndromes are: ##EQU2## that is, the syndromes S.sub.0, S.sub.1, S.sub.2, S.sub.3 can be obtained with the respective combinations of X.sub.j and Y.sub.j where:
v: the number of erasure words and error words, v=p+q, PA1 p: the number of error words, PA1 q: the number of erasure words, PA1 X.sub.j,: X.sub.j =.alpha..sup.lj and l.sub.j is the location of the jth error PA1 S.sub.k : syndrome, PA1 Y.sub.j : jth error value, and PA1 d: Hamming distance of the code.
According to several U.S. Pat. Nos., for example, Ozaki (4,852,099) and Okamoto et al. (4,677,622), we know the following:
If p=0 and q=4, then: ##EQU3##
When the number of erasure words q is from one to three, the number of error words p that can be accommodated becomes zero or one in accordance with Equation (1). To determine whether the actual value of p is zero, or one, or larger than one (in the situation that p is larger than one, the decoder cannot detect any error word from n symbols), reference must be made to a set of Forney Syndromes. If q is equal to one, then the Forney Syndromes are defined as: EQU T.sub.1 =S.sub.1 +S.sub.0 X.sub.1 EQU T.sub.2 =S.sub.2 +S.sub.1 X.sub.2 ( 7) EQU T.sub.3 =S.sub.3 +S.sub.2 X.sub.3
If q is equal to two, then the Forney Syndromes are defined as: EQU T.sub.1 =S.sub.2 +(X.sub.1 +X.sub.2) S.sub.1 +X.sub.1 X.sub.2 S.sub.0( 8) EQU T.sub.2 =S.sub.3 +(X.sub.1 +X.sub.2) S.sub.2 +X.sub.1 X.sub.2 S.sub.1
If q is equal to three, then the Forney Syndromes are defined as: EQU T.sub.1 =S.sub.3 +(X.sub.1 +X.sub.2 +X.sub.3) S.sub.2 +(X.sub.1 X.sub.2 +X.sub.2 X.sub.3 +X.sub.3 X.sub.1) S.sub.1 +X.sub.1 X.sub.2 X.sub.3 S.sub.0( 9)
In the condition that q is equal to one or two, the value of p can be determined according to the rules below:
(1) If the Forney Syndromes are all equal to zero, the value of p is zero.
(2) If the Forney Syndromes are all not equal to zero, the value of p is one.
(3) If at least one of the Forney Syndromes is equal to zero and at least one of the Forney Syndromes is not equal to zero, the decoder cannot correct any error word from n symbols.
Further, when q is equal to three, if the Forney Syndrome is equal to zero, then the decoder can correct error words from n symbols. When q is equal to three, and if the Forney Syndrome is not equal to zero, then the decoder cannot correct errors from n symbols.
When p is equal to one, the locations of unknown error words can be determined with the equations below: ##EQU4##
From the above Equations (3) to (11), the value of p can be determined only when the value of q is not equal to zero. In the situation that q is equal to zero, the value of p is determined by evaluating the following quantities: EQU S.sub.A =S.sub.1 S.sub.1 +S.sub.0 S.sub.2 EQU S.sub.B =S.sub.2 S.sub.2 +S.sub.1 S.sub.3 ( 12) EQU S.sub.C =S.sub.0 S.sub.3 +S.sub.1 S.sub.2
(1) If the three quantities are all equal to zero, then p is equal to one.
(2) If three quantities are all not equal to zero, then p is equal to two.
(3) If one or more of the quantities are equal to zero, and one or more of the quantities are not equal to zero, the decoder cannot correct the errors in n symbols. In situation (1), that is q=0 and p=1: ##EQU5## In situation (2), that is q=0 and p=2: ##EQU6##
From Equation (3) to Equation (13), X.sub.i and Y.sub.i can be determined by three types of calculations, such as adding, multiplying and inverting, except in the case of (p,q)=(2,0). (When q is not equal to zero, under the condition that i .ltoreq.q, X.sub.i can be obtained while the n symbols are being imported, and the values of Y.sub.i and l.sub.i can be obtained with the additional calculation of a logarithm.)
Under the condition that p=2 and q=0, there are several ways to solve for the values of X.sub.1 and X.sub.2 with Equation (14) and Equation (15). For example, the conventional method is to perform a "Chien's Search". In the method using a Chien's Search, at first, X.sub.1 is set to a predetermined value, and the value of X.sub.1 +X.sub.2 is set as SUM. Thus, X.sub.2 =SUM-X.sub.1 is obtained from Equation (14). Thereafter, X.sub.1 and X.sub.2 are substituted in Equation (15). If the value of the left side of the equation is not equal to the value of the right side, X.sub.1 is set to another predetermined value, referring to the former value. By repeatedly setting the value of X.sub.1, the value of X.sub.2 can be obtained. But the speed of decoding is very slow for several repetitions of the calculation in which different values of X.sub.1 and X.sub.2 are substituted in the processor-based program control decoder. The method therefore has a negative influence on the whole system, and is not practicable for calculating the actual values of X.sub.1 and X.sub.2.